Masala #1174
Maksimal kuch yig'ish #HARD
!Diqqat bu Maksimal kuch yig'ish masalasining qiyinroq versiyasi va sizning janglaringiz soni cheklangan.
Bu masalani yechish uchun siz quyidagi o'yin oxirida maksimal kuchga ega bo'lishingiz kerak. Xullas, o'yin quyidagicha:
Avvalo siz o'yinni X kuch bilan boshlaysiz. Sizda k ta raqib bilan bellashish imkoniyati bo'ladi va siz ulardan foydalanishingiz yoki foydalanmasligingiz mumkin. Keyinchalik esa sizda ketma-ket kelgan \(A_i\) kuchga ega bo'lgan raqiblarga to'qnash kelasiz. Agar u raqib sizdan kuchli bo'lsa siz hech narsa qila olmaysiz va agar unga hujum qilsangiz kuchingiz 0 ga tenglashadi. Lekin agar siz undan kuchli yoki kuchlaringiz teng bo'lsa siz unga hujum qilib mag'lub eta olasiz. Bu jang uchun sizning kuchingizga \(A_i\)(raqibning kuchi) qo'shiladi.
Eslatma: Siz raqib bilan jang qilishingiz yoki qilmasligingiz mumkin. Agar siz jang qilmasangiz, keyingi raqib tomonga yo'l olasiz. Lekin siz hech qachon oldin sizga uchragan raqib bilan qayta uchrasha olmaysiz!
1 - qatorda raqiblar soni n(1≤n≤25) va x (\(1<=x<=10^9\)) va k (1≤k≤\(20\))
Keyingi qatorda n ta son raqiblar kuchlari(1≤A≤\(10^9\)).
Yagona qatorda maksimal kuchni chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 3 2 2 6 5 8 |
10 |
Boshida bizda X = 3 bo'ladi va biz 2 kuchga ega bo'lgan raqibni yenga olamiz. Bundan keyin, X = 5. 6 kuchga ega raqibni yenga olmaymiz chunki 6>5. A = 5 bo'lgan raqibni yengamiz va X = 5+5 = 10. A = 8 ni ham yengib bo'lganimizda X = 10+8=18 bo'lar edi, ammo janglar soni cheklangan va javob x= 10.
Telegram kanalimizga obuna bo'ling